package com.zyk.grate_offer.class08;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author zhangsan
 * @date 2021/5/22 16:02
 */
public class Code01_ExpressionCompute {

    // 保证传入的表达式正确, 及不在方法内对表达式做验证
    // 表达式计算: 没有括号, + - * / %
    public static int g1(String expression) {
        if (expression == null || expression.isBlank()) return 0;
        Deque<String> deque = new LinkedList<>();
        int cur = 0;
        char[] str = expression.toCharArray();
        for (char c : str) {
            if (c == '-' || c == '+' || c == '*' || c == '/' || c == '%') {
                String stackTop;
                if (!deque.isEmpty() && ((stackTop = deque.peekLast()).equals("*") || stackTop.equals("/") || stackTop.equals("%"))) {
                    String computeSign = deque.pollLast();
                    int pre = Integer.parseInt(deque.pollLast());
                    cur = compute(pre, cur, computeSign);
                }
                deque.addLast(String.valueOf(cur));
                deque.addLast(String.valueOf(c));
                cur = 0;
            } else {
                cur = cur * 10 + (c - '0');
            }
        }
        deque.addLast(String.valueOf(cur));
        int ans = Integer.parseInt(deque.pollFirst());
        // 最后这个栈里, 都是 + - 数字了, 从前往后取
        while (!deque.isEmpty()) {
            String next = deque.pollFirst();
            if (next.equals("+") || next.equals("-")) {
                int nextNum = Integer.parseInt(deque.pollFirst());
                ans = compute(ans, nextNum, next);
            }
        }
        return ans;
    }

    static int index;

    // 保证传入的表达式正确, 及不在方法内对表达式做验证
    // 表达式计算: 小括号 + - * / %
    public static int calculate(String str) {
        if (str == null || str.isBlank()) return 0;
        index = 0;
        return f(str.toCharArray());
    }

    public static int f(char[] str) {
        Deque<String> deque = new LinkedList<>();
        int cur = 0;
        for (; index < str.length; index++) {
            if (str[index] == '(') {
                index++;
                cur = f(str);// 递归
                // 执行完f函数 index会变成对应右括号的位置
            } else if (str[index] == ')') {
                break;
            } else if (str[index] == '-' || str[index] == '+' || str[index] == '*' || str[index] == '/' || str[index] == '%') {
                String stackTop;
                if (!deque.isEmpty() && ((stackTop = deque.peekLast()).equals("*") || stackTop.equals("/") || stackTop.equals("%"))) {
                    String computeSign = deque.pollLast();
                    int pre = Integer.parseInt(deque.pollLast());
                    cur = compute(pre, cur, computeSign);
                }
                deque.addLast(String.valueOf(cur));
                deque.addLast(String.valueOf(str[index]));
                cur = 0;
            } else {
                cur = cur * 10 + (str[index] - '0');
            }
        }

        deque.addLast(String.valueOf(cur));
        int ans = Integer.parseInt(deque.pollFirst());
        // 最后这个栈里, 都是 + - 数字了, 从前往后取
        while (!deque.isEmpty()) {
            String next = deque.pollFirst();
            if (next.equals("+") || next.equals("-")) {
                int nextNum = Integer.parseInt(deque.pollFirst());
                ans = compute(ans, nextNum, next);
            }
        }
        return ans;
    }

    private static int compute(int a, int b, String computeSign) {
        if (computeSign.equals("+")) {
            return a + b;
        } else if (computeSign.equals("-")) {
            return a - b;
        } else if (computeSign.equals("*")) {
            return a * b;
        } else if (computeSign.equals("/")) {
            return a / b;
        } else if (computeSign.equals("%")) {
            return a % b;
        }
        return 0;
    }


    // for test
    public static void main(String[] args) {
//        String str = "34+1*2+4/3+7";
//        int ans = g1(str);
//        System.out.println(ans);


        String str = "1+2*(3+4*(2-1))+5";
        int ans = calculate(str);
        System.out.println(ans);
    }

}
